package m202405.d12;

import java.util.HashSet;
import java.util.Set;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/12 14:52
 */
public class Q160 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA;
        ListNode pb = headB;
        while (pa != pb) {
            if (pa == null) {
                pa = headB;
            }else {
                pa = pa.next;
            }
            if (pb == null) {
                pb = headA;
            }else {
                pb = pb.next;
            }
        }
        return pa;
    }

    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}
